# 快速排序使用分而治之的思想来获得和归并排序相同的优点，而不额外的使用存储。
# 找到第一个值当作比较值，有右端的和左端的一次跟比较值比较并不断移动，最后结果是rightmark在leftmark左端停止，然后rightmark是第一个小于比较值的值
# 所以将rightmark的值与第一个值进行交换，返回rightmark基准值的坐标用来切分数组，递归调用

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)   # 这样省的调用快速排序时手动输入左侧和右侧，这个还是只用输入alist

def quickSortHelper(alist,first,last):
    if first < last:
        splitpoint = partition(alist,first,last)    # 调用得到中间点并初步排序

        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)

# 某种意义上我甚至感觉不是递归，这个东西就是不断变小，当变得特别小的时候，alist的那部分就排好序了，也就是说最后每个小地方都排好序了，最后也就全部
# 排好序了。传入的都是一个数组，通过分而治之不断改变数组的小部分顺序直到所有的都改变。
def partition(alist,first,last):
    pivotvalue = alist[first]

    leftmark = first + 1
    rightmark = last

    done = False
    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivotvalue:
            rightmark = rightmark -1

        if rightmark < leftmark:    # 结束标志，右侧在左侧左边
            done = True
        else:   # 没有结束，并且这时候左右两边的数字正好和那个pivotvalue相反
            temp = alist[rightmark]
            alist[rightmark] = alist[leftmark]
            alist[leftmark] = temp

    temp = alist[rightmark]
    alist[rightmark] = pivotvalue
    alist[first] = temp
    return rightmark

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quickSort(alist)
    print(alist)
